package com.ljx.Dynamic;

import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * @author 李加喜
 * @Package com.ljx.Dynamic
 * @date 2021-11-03 23:03
 */

/**
 * N皇后
 */
public class Four {
    public static void main(String[] args) {
        Four four = new Four();
        List<List<String>> list = four.solveNQueens(4);
        System.out.println(list.toString());
    }
    // 路径 小于row的所有行
    // 选择条件 第row行都是可以进行放的
    // 结束条件  row达到最后一行了
    List<List<String>> res=new LinkedList<>();
    public List<List<String>> solveNQueens(int n) {
        String[][]nums=new String[n][n];
        for (int i=0;i<nums.length;i++){
            Arrays.fill(nums[i], ".");
        }
        // 从0开始  第一行
        dp(nums,0);
        return res;
    }

    private void dp(String[][] nums, int i) {
        if (i==nums.length-1){
            res.add(Collections.singletonList(Arrays.toString(nums[i])));
            return;
        }
        // 当前有多少列
        int n=nums[i].length;
        for (int col=0;col<n;col++){
            // 检验当前这一类是否可以放
            if (!isCheck(nums,i,col)){
                continue;
            }
            nums[i][col]="Q";
            dp(nums,i+1);
            nums[i][col]=".";
        }
    }

    /**
     *
     * @param nums
     * @param m 行
     * @param col 列
     * @return
     */
    private boolean isCheck(String[][] nums, int m, int col) {
        int n= nums.length;
        // 检查列是否有皇后互相冲突
        for (int i = 0; i < n; i++) {
            if (nums[i][col].equals("Q")){
                return false;
            }
        }
        // 检查右上方是否有皇后互相冲突
        for (int i = m - 1, j = col + 1;
             i >= 0 && j < n; i--, j++) {
            if ("Q".equals(nums[i][j])){
                return false;
            }
        }
        // 检查左上方是否有皇后互相冲突
        for (int i = m - 1, j = col - 1;
             i >= 0 && j >= 0; i--, j--) {
            if ("Q".equals(nums[i][j])){
                return false;
            }
        }
        return true;
    }
}
